package com.dong.algorithm.novice.search;

import java.util.Arrays;

/**
 * 局部最小值问题
 * 返回数组中任意一个局部最小值
 *
 * @author by jiweidong on 2021/11/24.
 */
public class Arg04_BinarySearchAnyOneMinIndex {

    public static void main(String[] args) {
        int[] arr = {8, 3, 2, 3, 6, 5, 7, 8, 9, 10};
        int ans = oneMinIndex(arr);
        System.out.println(ans);

        int maxLen = 10;
        int maxValue = 100;
        int testTimes = 10000;

        int[] array = null;
        int minIdx = -999;
        try {
            for (int i = 0; i < testTimes; i++) {
                array = randomArray(maxLen, maxValue);
                minIdx = oneMinIndex(array);
                if (!check(array, minIdx)) {
                    System.out.println("出错了!");
                    System.out.println(Arrays.toString(array));
                    System.out.println(minIdx);
                }
                array = null;
                minIdx = -999;
            }
        } catch (Exception e) {
            System.out.println("出异常了!");
            System.out.println(Arrays.toString(array));
            System.out.println(minIdx);
            e.printStackTrace();
        }
        System.out.println("对数结束");
    }

    // arr 整体无序
    // arr 相邻的数不相等
    public static int oneMinIndex(int[] arr) {

        // 先处理边界
        if (arr == null || arr.length == 0) {
            return -1;
        }

        int N = arr.length;

        if (N == 1) {
            return 0;
        }
        if (N == 2) {
            return arr[0] < arr[1] ? 0 : 1;
        }

        int L = 0;
        int R = N - 1;
        while (L <= R) {
            if (arr[L] < arr[L + 1]) {
                return L;
            }
            if (arr[R] < arr[R - 1]) {
                return R;
            }
            int mid = (L + R) / 2;
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                if (arr[mid] > arr[mid - 1]) {
                    R = mid - 1;
                } else {
                    L = mid + 1;
                }
            }
        }
        return -1;
    }

    // arr 整体无序
    // arr 相邻的数不相等
    public static int[] randomArray(int maxLen, int maxValue) {
        int len = (int) (Math.random() * maxLen);
        int[] arr = new int[len];
        if (len == 0) {
            return arr;
        }
        arr[0] = (int) (Math.random() * maxValue);
        for (int i = 1; i < len; i++) {
            do {
                arr[i] = (int) (Math.random() * maxValue);
            } while (arr[i] == arr[i - 1]);
        }
        return arr;
    }

    // 对数器
    public static boolean check(int[] arr, int minIndex) {
        if (arr.length == 0) {
            return minIndex == -1;
        }
        int left = minIndex - 1;
        int right = minIndex + 1;
//        boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
        boolean leftBigger = left < 0 || arr[left] > arr[minIndex];
//        boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true;
        boolean rightBigger = right >= arr.length || arr[right] > arr[minIndex];
        return leftBigger && rightBigger;
    }

}
